package week3;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


/**
 *
 *
 * 47. 全排列 II
 * https://leetcode-cn.com/problems/permutations-ii/
 *
 * 执行结果：  通过  显示详情
 *
 * 添加备注
 * 执行用时：1 ms, 在所有 Java 提交中击败了99.30% 的用户
 * 内存消耗：39.2 MB, 在所有 Java 提交中击败了46.29% 的用户
 * 通过测试用例：33 / 33
 * 炫耀一下:
 *
 *
 *
 */
public class Week3PermutationsII {



    public void backtrack(int[] nums, List<List<Integer>> ans, int index, List<Integer> perm, boolean[] visitor) {
        if(index == nums.length) {
            ans.add(new ArrayList<Integer>(perm));
            return;
        }
        for(int size = 0; size < nums.length; size++) {
            if(visitor[size] || (size > 0 && nums[size] == nums[size - 1] && !visitor[size - 1])) {
                continue;
            }
            perm.add(nums[size]);
            visitor[size] = true;
            backtrack(nums, ans, index + 1, perm, visitor);
            visitor[size] = false;
            perm.remove(index);

        }
    }

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        boolean[] visitor = new boolean[nums.length];
        List<Integer> perm = new ArrayList<Integer>();

        backtrack(nums, ans, 0, perm, visitor);
        return ans;
    }
}
